package org.aplombh.java.awcing.basic.graph.graphTraversal.bfs;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

import javafx.util.Pair;

/**
 * 给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
 * <p>
 * 最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
 * <p>
 * 请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
 * <p>
 * 数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
 * <p>
 * 输入格式
 * 第一行包含两个整数 n 和 m。
 * <p>
 * 接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
 * <p>
 * 输出格式
 * 输出一个整数，表示从左上角移动至右下角的最少移动次数。
 * <p>
 * 数据范围
 * 1≤n,m≤100
 * 输入样例：
 * 5 5
 * 0 1 0 0 0
 * 0 1 0 1 0
 * 0 0 0 0 0
 * 0 1 1 1 0
 * 0 0 0 1 0
 * 输出样例：
 * 8
 */
public class Mazes_844 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] graph = new int[Mazes.N][Mazes.N];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }

        Mazes mazes = new Mazes(graph, n, m);
        System.out.println(mazes.bfs());
    }
}

class Mazes {
    public static final int N = 110;
    private final int[][] graph; // 存储迷宫地图 Store maze map
    private final int[][] distance = new int[N][N];  // 存储距离 Store distance
    private final Pair<Integer, Integer>[] queue = new Pair[N * N];   // 存储节点的x和y坐标 store x and y coordinates of the point
    private final int n, m;
    private int head = 0; // 对头
    private int tail = 0; // 队尾

    Mazes(int[][] graph, int n, int m) {
        this.graph = graph;
        this.n = n;
        this.m = m;
        queue[0] = new Pair<>(0, 0);
        for (int i = 0; i < N; i++) {
            // 初始距离设为-1，标志未访问过
            Arrays.fill(distance[i],-1);
//            for (int j = 0; j < N; j++) {
//                distance[i][j] = -1;
//            }
        }
        distance[0][0] = 0;
    }

    int bfs() {

        // 向四个方向移动的 moving in four directions
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        // 队列中还有数据
        while (head <= tail) {
            // 队头出队 The head of the queue dequeue
            Pair<Integer, Integer> t = queue[head++];

            // 依次遍历四个方向
            for (int i = 0; i < 4; i++) {

                int x = t.getKey() + dx[i];
                int y = t.getValue() + dy[i];

                // 如果可以走，将该点加入队列，距离+1 If you can go this point, add the point to the queue, distance +1
                // 该点可以走，并且未走过
                if (x >= 0 && x < n && y >= 0 && y < n && graph[x][y] == 0 && distance[x][y] == -1) {

                    // 能从t点到达该点，第一次到达，为到达该结点的最近距离，将该结点的距离设为t点距离+1
                    distance[x][y] = distance[t.getKey()][t.getValue()] + 1;
                    // 将该点入队
                    queue[++tail] = new Pair<>(x, y);
                }
            }
        }
        return distance[n - 1][m - 1];
    }
}

